package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;

/**
 * 分治思想，三步走
 * 一：判断最底下的情况
 * 二：递归调用多个分支
 * 三：合并多个分支返回的结果
 */
public class POne04二叉树的最大深度{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxDepth(TreeNode root) {
        // 一：判断最底下的情况
        if(root==null){
            return 0;
        }
        // 二：递归调用多个分支
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        // 三：合并多个分支返回的结果
        return Math.max(left,right)+1;
    }

//    public int maxDepth(TreeNode root) {
//        // 一：判断最底下的情况
//        if(root==null){
//            return 0;
//        }
//        dfs(root);
//        return maxD;
//    }
//    int deep=0;
//    int maxD = 0;
//    void dfs(TreeNode root){
//        if(root==null){
//            return;
//        }
//        deep++;
//        maxD=Math.max(maxD,deep);
//        dfs(root.left);
//        dfs(root.right);
//        deep--;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne04二叉树的最大深度().new Solution();
        int i = solution.maxDepth(TreeNode.generatorTreeNode("3,9,20,null,null,15,7"));
        System.out.println(i);
    }
}